package com.arithmeticEveryDay.blueBridge;

import java.util.Scanner;

/*


        0   1   2   3   4   5   6   7
  w v   0   0   0   0   0   0   0   0
0(2,3)  0   0   3   3   3   3   3   3
1(3,5)  0   0   3   5   5   8   8   8
2(4,6)  0   0   3   5   6   8   9   11
3(5,7)  0   0   3   5   6   8   9   11

dp[i][j]的含义：
剩余容量为j，剩余可选物品为[0, j]，其它物品已经被选完的情况下的最优解
以dp[3][7]为例：
确定dp[3][7]需要比较dp[2][7], value[3] + dp[1][7-4]和value[3] + dp[2][7-4]
但由于dp[1][7-3]与dp[2][7-4]之前已经比较过，所以只需要选择dp[2][7-4]进行比较
同理我们可以推出：
dp[i][j] = max(dp[i-1][j], value[i-1] + dp[i-1][j-weight[i-1])

7 4
2 3
3 5
4 6
5 7

 */
public class Main303 {
    int[] weight;
    int[] value;
    

    private Main303(int[] weight, int[] value) {
        super();
        this.weight = weight;
        this.value = value;
    }

    private int maxValue(int totalWeight) {
        int n = weight.length;
        int[][] dp = new int[n+1][totalWeight+1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= totalWeight; j++) {
                if (j >= weight[i-1]) {
                    dp[i][j] = Math.max(dp[i-1][j], value[i-1] + dp[i-1][j-weight[i-1]]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        /*
        for (int i = 0; i <= n; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        */
        return dp[n][totalWeight];
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int totalWeight = scan.nextInt();
        int n = scan.nextInt();
        int[] weight = new int[n];
        int[] value = new int[n];
        
        for (int i = 0; i < n; i++) {
            weight[i] = scan.nextInt();
            value[i] = scan.nextInt();
        }
        Main303 m = new Main303(weight, value);
        System.out.println(m.maxValue(totalWeight));
    }

}
